home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 February: Tool Chest / Dev.CD Feb 95 / Dev.CD Feb 95.toast / Tool Chest / Development Tools & Languages / Dylan Related / Mindy-1.1 (sources only) / mindy-1.1 / interp / gc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-26  |  8.6 KB  |  353 lines  |  [TEXT/ttxt]
  1. /**********************************************************************\
  2. *
  3. *  Copyright (c) 1994  Carnegie Mellon University
  4. *  All rights reserved.
  5. *  
  6. *  Use and copying of this software and preparation of derivative
  7. *  works based on this software are permitted, including commercial
  8. *  use, provided that the following conditions are observed:
  9. *  
  10. *  1. This copyright notice must be retained in full on any copies
  11. *     and on appropriate parts of any derivative works.
  12. *  2. Documentation (paper or online) accompanying any system that
  13. *     incorporates this software, or any part of it, must acknowledge
  14. *     the contribution of the Gwydion Project at Carnegie Mellon
  15. *     University.
  16. *  
  17. *  This software is made available "as is".  Neither the authors nor
  18. *  Carnegie Mellon University make any warranty about the software,
  19. *  its performance, or its conformity to any specification.
  20. *  
  21. *  Bug reports, questions, comments, and suggestions should be sent by
  22. *  E-mail to the Internet address "gwydion-bugs@cs.cmu.edu".
  23. *
  24. ***********************************************************************
  25. *
  26. * $Header: gc.c,v 1.13 94/07/26 00:39:52 wlott Exp $
  27. *
  28. * This file is the garbage collector.
  29. *
  30. \**********************************************************************/
  31.  
  32. #include <stdio.h>
  33. #include <string.h>
  34.  
  35. #include "mindy.h"
  36. #include "class.h"
  37. #include "gc.h"
  38. #include "weak.h"
  39. #include "table.h"
  40.  
  41. extern void scavenge_thread_roots(void);
  42. extern void scavenge_bool_roots(void);
  43. extern void scavenge_class_roots(void);
  44. extern void scavenge_coll_roots(void);
  45. extern void scavenge_func_roots(void);
  46. extern void scavenge_instance_roots(void);
  47. extern void scavenge_interp_roots(void);
  48. extern void scavenge_list_roots(void);
  49. extern void scavenge_num_roots(void);
  50. extern void scavenge_obj_roots(void);
  51. extern void scavenge_vec_roots(void);
  52. extern void scavenge_str_roots(void);
  53. extern void scavenge_char_roots(void);
  54. extern void scavenge_symbol_roots(void);
  55. extern void scavenge_type_roots(void);
  56. extern void scavenge_module_roots(void);
  57. extern void scavenge_value_roots(void);
  58. extern void scavenge_debug_roots(void);
  59. extern void scavenge_handler_roots(void);
  60. extern void scavenge_load_roots(void);
  61. extern void scavenge_nlx_roots(void);
  62. extern void scavenge_driver_roots(void);
  63. extern void scavenge_buffer_roots(void);
  64. extern void scavenge_weak_roots(void);
  65. extern void scavenge_brkpt_roots(void);
  66. extern void scavenge_table_roots(void);
  67.  
  68.  
  69. #define CHECKGC 1
  70.  
  71. boolean TimeToGC = FALSE;
  72.  
  73. struct block {
  74.     struct block *next;
  75.     void *base;
  76.     void *end;
  77.     void *fill;
  78. };
  79.  
  80. #define BLOCK_SIZE (128*1024)
  81. #define BYTES_CONSED_BETWEEN_GCS (2*1024*1024)
  82.  
  83. static struct block *FreeBlocks = 0;
  84. static struct block *UsedBlocks = 0;
  85. #if CHECKGC
  86. static struct block *OldBlocks = 0;
  87. #endif
  88. static struct block *cur_block = 0;
  89. static void *cur_fill = 0, *cur_end = 0;
  90. static int BytesInUse = 0;
  91. static int GCTrigger = BYTES_CONSED_BETWEEN_GCS;
  92.  
  93. static int bytes_in_use(void)
  94. {
  95.     if (cur_block)
  96.     return BytesInUse + (cur_fill - cur_block->base);
  97.     else
  98.     return BytesInUse;
  99. }
  100.  
  101. void *raw_alloc(int bytes)
  102. {
  103.     void *result;
  104.  
  105.     if (bytes < 0)
  106.     lose("Can't allocate a negative number of bytes: %d", bytes);
  107.  
  108.     /* round bytes up to the next dual-word boundy. */
  109.     bytes = (bytes + 7) & ~7;
  110.  
  111.     if (bytes > BLOCK_SIZE - sizeof(struct block))
  112.     lose("Can't allocate %d bytes, %d at most.",
  113.          bytes, BLOCK_SIZE - sizeof(struct block));
  114.  
  115.     if (cur_fill + bytes > cur_end) {
  116.     struct block *block;
  117.  
  118.     if (FreeBlocks) {
  119.         block = FreeBlocks;
  120.         FreeBlocks = block->next;
  121.     }
  122.     else {
  123.         block = malloc(BLOCK_SIZE);
  124.         block->base = (void *)block + sizeof(struct block);
  125.         block->end = (void *)block + BLOCK_SIZE;
  126.     }
  127.     block->next = 0;
  128.  
  129.     if (cur_block) {
  130.         BytesInUse += cur_fill - cur_block->base;
  131.         cur_block->fill = cur_fill;
  132.         cur_block->next = block;
  133.         if (BytesInUse > GCTrigger)
  134.         TimeToGC = TRUE;
  135.     }
  136.     else
  137.         UsedBlocks = block;
  138.  
  139.     cur_block = block;
  140.     cur_fill = block->base;
  141.     cur_end = block->end;
  142.     }
  143.  
  144.     result = cur_fill;
  145.     cur_fill += bytes;
  146.  
  147.     return result;
  148. }
  149.  
  150. obj_t alloc(obj_t class, int bytes)
  151. {
  152. #if CHECKGC
  153.     unsigned int *ptr;
  154. #else
  155.     void *ptr;
  156. #endif
  157.     obj_t result;
  158.  
  159.     if (class == NULL)
  160.     lose("Tried to allocate a class that hasn't been created yet.");
  161.  
  162. #if CHECKGC
  163.     if (class != ptr_obj(NULL)
  164.       && *obj_ptr(int *, class) == 0xfacefeed)
  165.     lose("Tried to allocate a class that wasn't scavenged.");
  166.  
  167.     ptr = raw_alloc(bytes + sizeof(int)*2);
  168.     ptr[0] = 0xbeadbabe;
  169.     ptr[1] = bytes;
  170.  
  171.     result = ptr_obj(ptr + 2);
  172. #else
  173.     ptr = raw_alloc(bytes);
  174.     result = ptr_obj(ptr);
  175. #endif
  176.  
  177.     obj_ptr(struct object *, result)->class = class;
  178.  
  179.     return result;
  180. }
  181.  
  182.  
  183. struct forwarding_pointer {
  184.     obj_t marker;
  185.     obj_t new_value;
  186. };
  187.  
  188. void scavenge(obj_t *addr)
  189. {
  190.     obj_t obj = *addr;
  191.  
  192.     if (obj_is_ptr(obj)) {
  193.     obj_t class = obj_ptr(struct object *, obj)->class;
  194.     if (class == ForwardingMarker)
  195.         *addr = obj_ptr(struct forwarding_pointer *, obj)->new_value;
  196.     else
  197.         *addr = obj_ptr(struct class *, class)->transport(obj);
  198.     }
  199. }
  200.  
  201. obj_t transport(obj_t obj, int bytes)
  202. {
  203. #if CHECKGC
  204.     unsigned int *new;
  205.     unsigned int *ptr = obj_ptr(unsigned int *, obj) - 2;
  206. #else
  207.     void *new;
  208. #endif
  209.     obj_t new_obj;
  210.  
  211. #if CHECKGC
  212.     if (ptr[0] != 0xbeadbabe)
  213.     lose("Someone called transport with a bogus object.");
  214.     if (ptr[1] != bytes)
  215.     lose("Someone told transport that %d byte object was %d bytes.",
  216.          ptr[1], bytes);
  217.  
  218.     new = raw_alloc(bytes + sizeof(int)*2);
  219.     new_obj = ptr_obj(new + 2);
  220.  
  221.     memcpy(new, ptr, bytes + sizeof(int)*2);
  222. #else
  223.     new = raw_alloc(bytes);
  224.     new_obj = ptr_obj(new);
  225.     memcpy(new, obj_ptr(void *, obj), bytes);
  226. #endif
  227.  
  228.     obj_ptr(struct forwarding_pointer *, obj)->marker = ForwardingMarker;
  229.     obj_ptr(struct forwarding_pointer *, obj)->new_value = new_obj;
  230.  
  231.     return new_obj;
  232. }
  233.  
  234. static void scavenge_newspace(void)
  235. {
  236.     struct block *block = UsedBlocks;
  237.     void *ptr, *end;
  238.     obj_t class;
  239.     int bytes;
  240.  
  241.     while (block != 0) {
  242.     ptr = block->base;
  243.     /* The reason for this double loop is so that we don't have to */
  244.     /* do the block->next conditional each time around the inner loop. */
  245.     while (ptr < (end = (block->next ? block->fill : cur_fill))) {
  246.         do {
  247. #if CHECKGC
  248.         unsigned int *header = ptr;
  249.         if (header[0] != 0xbeadbabe)
  250.             lose("Scavenge_newspace found a bogus object.");
  251.         ptr += sizeof(int)*2;
  252. #endif
  253.         scavenge((obj_t *)ptr);
  254.         class = *(obj_t *)ptr;
  255.         bytes = obj_ptr(struct class *, class)->scavenge(ptr);
  256. #if CHECKGC
  257.         if (header[1] != bytes)
  258.             lose("Some scavenger claimed a %d byte object "
  259.              "was %d bytes.",
  260.              header[1], bytes);
  261. #endif
  262.         ptr += (bytes + 7) & ~7;
  263.         } while (ptr < end);
  264.     }
  265.     block = block->next;
  266.     }
  267. }
  268.  
  269. void collect_garbage(void)
  270. {
  271.     struct block *old_blocks = UsedBlocks;
  272.     int bytes_at_start = bytes_in_use();
  273.     int bytes_at_end;
  274.  
  275.     fprintf(stderr, "[GCing with %d bytes in use...", bytes_at_start);
  276.     fflush(stderr);
  277.  
  278.     TimeToGC = FALSE;
  279.     BytesInUse = 0;
  280.     UsedBlocks = 0;
  281.     cur_block = 0;
  282.     cur_fill = 0;
  283.     cur_end = 0;
  284.  
  285.     scavenge_thread_roots();
  286.     scavenge_bool_roots();
  287.     scavenge_class_roots();
  288.     scavenge_coll_roots();
  289.     scavenge_func_roots();
  290.     scavenge_instance_roots();
  291.     scavenge_interp_roots();
  292.     scavenge_list_roots();
  293.     scavenge_num_roots();
  294.     scavenge_obj_roots();
  295.     scavenge_vec_roots();
  296.     scavenge_str_roots();
  297.     scavenge_char_roots();
  298.     scavenge_symbol_roots();
  299.     scavenge_type_roots();
  300.     scavenge_module_roots();
  301.     scavenge_value_roots();
  302.     scavenge_debug_roots();
  303.     scavenge_handler_roots();
  304.     scavenge_load_roots();
  305.     scavenge_nlx_roots();
  306.     scavenge_driver_roots();
  307.     scavenge_buffer_roots();
  308.     scavenge_weak_roots();
  309.     scavenge_brkpt_roots();
  310.     scavenge_table_roots();
  311.  
  312.     scavenge_newspace();
  313.  
  314.     break_weak_pointers();
  315.  
  316. #if CHECKGC
  317.     {
  318.     struct block *block, *next;
  319.     for (block = OldBlocks; block != NULL; block = next) {
  320.         next = block->next;
  321.         block->next = FreeBlocks;
  322.         FreeBlocks = block;
  323.     }
  324.     OldBlocks = NULL;
  325.     for (block = old_blocks; block != NULL; block = next) {
  326.         unsigned int *ptr;
  327.         next = block->next;
  328.         block->next = OldBlocks;
  329.         OldBlocks = block;
  330.         for (ptr = block->base; ptr < (unsigned int *)block->end; ptr++)
  331.         *ptr = 0xfacefeed;
  332.     }
  333.     }
  334. #else
  335.     while (old_blocks != 0) {
  336.     struct block *next = old_blocks->next;
  337.     old_blocks->next = FreeBlocks;
  338.     FreeBlocks = old_blocks;
  339.     old_blocks = next;
  340.     }
  341. #endif
  342.  
  343.     bytes_at_end = bytes_in_use();
  344.     GCTrigger = bytes_at_end + BYTES_CONSED_BETWEEN_GCS;
  345.  
  346.     fprintf(stderr, "reclaimed %d leaving %d]\n",
  347.         bytes_at_start - bytes_at_end,
  348.         bytes_at_end);
  349.     fflush(stderr);
  350.  
  351.     table_gc_hook();
  352. }
  353.